package com.cat.dataStructure03;

import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-score-of-an-array-after-marking-all-elements/https://leetcode.cn/problems/find-score-of-an-array-after-marking-all-elements/
 * @create 2025/11/8 15:27
 * @since JDK17
 */

public class Solution22 {
    public long findScore(int[] nums) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });
        long ans = 0;
        int n = nums.length;
        boolean[] h = new boolean[n + 1];
        for (int i = 0; i < n; i++) {
            heap.add(new int[] {nums[i], i});
        }
        while (!heap.isEmpty()) {
            var q = heap.poll();
            if (!h[q[1]]) { // 没有用过
                ans += q[0];
                h[Math.max(0, q[1] - 1)] = true;
                h[q[1] + 1] = true;
            }
        }
        return ans;
    }
}
